{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check If Word Is Valid After Substitutions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isValid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #检查替换后的词是否有效"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "给你一个字符串 <code>s</code> ，请你判断它是否 <strong>有效</strong> 。\n",
    "<p>字符串 <code>s</code> <strong>有效</strong> 需要满足：假设开始有一个空字符串 <code>t = \"\"</code> ，你可以执行 <strong>任意次</strong> 下述操作将<strong> </strong><code>t</code><strong> 转换为 </strong><code>s</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>将字符串 <code>\"abc\"</code> 插入到 <code>t</code> 中的任意位置。形式上，<code>t</code> 变为 <code>t<sub>left</sub> + \"abc\" + t<sub>right</sub></code>，其中 <code>t == t<sub>left</sub> + t<sub>right</sub></code> 。注意，<code>t<sub>left</sub></code> 和 <code>t<sub>right</sub></code> 可能为 <strong>空</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果字符串 <code>s</code> 有效，则返回 <code>true</code>；否则，返回 <code>false</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aabcbc\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>\n",
    "\"\" -&gt; \"<strong>abc</strong>\" -&gt; \"a<strong>abc</strong>bc\"\n",
    "因此，\"aabcbc\" 有效。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcabcababcc\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>\n",
    "\"\" -&gt; \"<strong>abc</strong>\" -&gt; \"abc<strong>abc</strong>\" -&gt; \"abcabc<strong>abc</strong>\" -&gt; \"abcabcab<strong>abc</strong>c\"\n",
    "因此，\"abcabcababcc\" 有效。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abccba\"\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>执行操作无法得到 \"abccba\" 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code> 由字母 <code>'a'</code>、<code>'b'</code> 和 <code>'c'</code> 组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-word-is-valid-after-substitutions](https://leetcode.cn/problems/check-if-word-is-valid-after-substitutions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-word-is-valid-after-substitutions](https://leetcode.cn/problems/check-if-word-is-valid-after-substitutions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aabcbc\"', '\"abcabcababcc\"', '\"abccba\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        self.isValid = True\n",
    "        self.maxDepth(root)\n",
    "        return self.isValid\n",
    "\n",
    "\n",
    "    def maxDepth(self, root):\n",
    "        if not root: return 0\n",
    "        if not self.isValid: return -999\n",
    "        leftMaxDepth = self.maxDepth(root.left)\n",
    "        rightMaxDepth = self.maxDepth(root.right)\n",
    "        if abs(leftMaxDepth - rightMaxDepth) > 1:\n",
    "            self.isValid = False\n",
    "        return max(leftMaxDepth, rightMaxDepth) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        while 'abc' in s:\n",
    "            s = s.replace('abc', '')\n",
    "        return s == ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        while \"abc\" in s:\n",
    "            s = s.replace('abc','')\n",
    "        if s == '':\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n // 3 * 3 != n or 'ac' in s or 'bb' in s:\n",
    "            return False\n",
    "        # 栈\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if len(stack) >= 2 and stack[-2] == 'a' and stack[-1] == 'b' and c == 'c':\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(c)\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        while \"abc\" in s:\n",
    "            s = s.replace(\"abc\", '')\n",
    "\n",
    "\n",
    "\n",
    "        return s == ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        while 'abc' in s:\n",
    "            s = s.replace('abc', '')\n",
    "        return s == ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if s[0] != 'a' or n // 3 * 3 != n or 'ac' in s or 'bb' in s:\n",
    "            return False\n",
    "        # 栈\n",
    "        st = []\n",
    "        for c in map(ord, s):\n",
    "            if c > ord('a') and (len(st) == 0 or c - st.pop() != 1):\n",
    "                return False\n",
    "            if c < ord('c'):\n",
    "                st.append(c)\n",
    "        return len(st) == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n // 3 * 3 != n:\n",
    "            return False\n",
    "        # 栈\n",
    "        st = []\n",
    "        for c in map(ord, s):\n",
    "            if c > 97 and (not st or c - st.pop() != 1):\n",
    "                return False\n",
    "            if c < 99:\n",
    "                st.append(c)\n",
    "        return len(st) == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            stack.append(c)\n",
    "            if len(stack) >= 3:\n",
    "                if ''.join(stack[-3:]) == 'abc':\n",
    "                    stack[-3:] = []\n",
    "\n",
    "        return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        if len(s)%3 != 0:\n",
    "            return False\n",
    "        update = True\n",
    "        while(len(s)>0 and update):\n",
    "            update = False\n",
    "            for i in range(len(s)-2):\n",
    "                if s[i:i+3]=='abc':\n",
    "                    s = s[:i] + s[i+3:]\n",
    "                    update = True\n",
    "                    break\n",
    "        if len(s)==0:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        mstr = s \n",
    "        while len(mstr) > 0:\n",
    "            left = self.locate_abc(mstr)\n",
    "            if left is None:\n",
    "                return False\n",
    "            mstr = mstr[:left]+mstr[left+3:]\n",
    "        return True\n",
    "\n",
    "    def locate_abc(self, s):\n",
    "        if len(s) < 3:\n",
    "            return None\n",
    "        for aidx in range(len(s)-2):\n",
    "            if s[aidx:aidx+3] == 'abc':\n",
    "                return aidx \n",
    "        return None "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        _s = s.replace('abc', '')\n",
    "        while len(_s) != len(s):\n",
    "            s = _s\n",
    "            _s = s.replace('abc', '')\n",
    "        return len(s) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        # 可以使用替换的方法 -- if \"abc\" in s : s.replace(\"abc\",\"\",1)\n",
    "        \n",
    "        while (\"abc\" in s):\n",
    "            s = s.replace(\"abc\",\"\",1)\n",
    "\n",
    "        if not s: return True\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        for _ in range(len(s)//3):\n",
    "            s = s.replace('abc', '')\n",
    "        return False if s else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        if len(s) % 3:\n",
    "            return False\n",
    "\n",
    "        st = []\n",
    "        for c in map(ord, s):\n",
    "            if c > 97 and (not st or c - st.pop() != 1):\n",
    "                return False\n",
    "            if c < 99:\n",
    "                st.append(c)\n",
    "        return not st\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n // 3 * 3 != n:\n",
    "            return False\n",
    "        # 栈\n",
    "        st = []\n",
    "        for c in map(ord, s):\n",
    "            if c > 97 and (len(st) == 0 or c - st.pop() != 1):\n",
    "                return False\n",
    "            if c < 99:\n",
    "                st.append(c)\n",
    "        return len(st) == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        l = n // 3\n",
    "        if l * 3 != n:\n",
    "            return False\n",
    "        for _ in range(l):\n",
    "            s = s.replace('abc', '', 1)\n",
    "        return not s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n // 3 * 3 != n:\n",
    "            return False\n",
    "        # 栈\n",
    "        st = []\n",
    "        for c in map(ord, s):\n",
    "            if c > ord('a') and (len(st) == 0 or c - st.pop() != 1):\n",
    "                return False\n",
    "            if c < ord('c'):\n",
    "                st.append(c)\n",
    "        return len(st) == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        while True:\n",
    "            c=s.replace(\"abc\",\"\")\n",
    "            if c==\"\":\n",
    "                return True\n",
    "            elif c==s!=\"\":\n",
    "                return False\n",
    "            s=c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        if len(s) % 3:\n",
    "            return False\n",
    "        t = []\n",
    "        for c in s:\n",
    "            t.append(c)\n",
    "            if ''.join(t[-3:]) == 'abc':\n",
    "                t[-3:] = []\n",
    "        return not t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n%3:\n",
    "            return False\n",
    "        st = []\n",
    "        for i in s:\n",
    "            if i == 'c':\n",
    "                if len(st) < 2 or st[-1] != 'b' or st[-2] != 'a':\n",
    "                    return False\n",
    "                st.pop()\n",
    "                st.pop()\n",
    "            else:\n",
    "                st.append(i)\n",
    "        return not st\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        while 'abc' in s:\n",
    "            s = s.replace('abc','')\n",
    "        return not s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        ans = []\n",
    "        for i in s:\n",
    "            if i == 'a': ans.append(i)\n",
    "            elif i == 'b':\n",
    "                if not ans or ans[-1] != 'a': return False\n",
    "                else: ans.append(i)\n",
    "            else:\n",
    "                if not ans or ans[-1] != 'b': return False\n",
    "                else: \n",
    "                    ans.pop()\n",
    "                    ans.pop()\n",
    "        return not ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            stack.append(c)\n",
    "            if c == 'c':\n",
    "                if len(stack) < 3 or ''.join(stack[-3:]) != 'abc':\n",
    "                    return False\n",
    "                stack[-3:] = []\n",
    "\n",
    "        return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        res =  s\n",
    "        while res and \"abc\" in res:\n",
    "            res = res.replace(\"abc\", \"\")\n",
    "        return res == \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isValid(self, s):\n",
    "        while True:\n",
    "            s_ = s.replace(\"abc\", \"\")\n",
    "            if s_ == \"\": return True\n",
    "            elif s_ == s != \"\": return False\n",
    "            s = s_        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        s1 = \"\"\n",
    "\n",
    "        for item in s:\n",
    "            s1 += item\n",
    "            if len(s1) >= 3:\n",
    "                if s1.endswith(\"abc\"):\n",
    "                    s1 = s1[:-3]\n",
    "\n",
    "        if s1 == \"\":\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        while s:\n",
    "            flg = 1\n",
    "            i = 0\n",
    "            while i < len(s)-2:\n",
    "                if s[i:i+3] == \"abc\":\n",
    "                    s = s[:i]+s[i+3:]\n",
    "                    flg = 0\n",
    "                    break\n",
    "                i += 1\n",
    "            if flg:\n",
    "                return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isValid(self, S):\n",
    "        if not S:\n",
    "            print(False)\n",
    "            return False\n",
    "\n",
    "        while \"abc\" in S:\n",
    "            S = S.replace(\"abc\", \"\")\n",
    "        \n",
    "        print(not S)\n",
    "        return not S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        if len(s)<=2:\n",
    "            return False\n",
    "        stack=[s[0],s[1]]\n",
    "        for i in range(2,len(s)):\n",
    "            stack.append(s[i])\n",
    "            if ''.join(stack[-3:])=='abc':\n",
    "                stack[-3:]=[]\n",
    "        return not stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isValid(self, s):\n",
    "        d=deque()\n",
    "        for c in map(ord,s):\n",
    "            if c==ord('a'):\n",
    "                d.append(c)\n",
    "            elif c==ord('b'):\n",
    "                if len(d)==0 or c-d[-1]!=1:\n",
    "                    return False\n",
    "                else:\n",
    "                    d[-1]=c\n",
    "            else:\n",
    "                if len(d)==0 or c-d[-1]!=1:\n",
    "                    return False\n",
    "                else:\n",
    "                    d.pop()\n",
    "                    \n",
    "        return len(d)==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "\n",
    "\n",
    "        for i in range(len(s)-4, -1, -1):\n",
    "            # print(i)\n",
    "            if s[i] == 'a':\n",
    "                if s[i+1] == 'b':\n",
    "                    # print(s[i+1])\n",
    "                    print(i+2)\n",
    "                    if s[i+2] == 'c':\n",
    "                        s = s[0:i] + s[i+3:]\n",
    "\n",
    "        if len(s) == 3:\n",
    "            if s == 'abc':\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        if len(s) == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        lis = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] != \"c\":\n",
    "                lis.append(s[i])\n",
    "            else:\n",
    "                try:\n",
    "                    if lis.pop(-1) == \"b\" and lis.pop(-1) ==\"a\":\n",
    "                        pass\n",
    "                    else:\n",
    "                        return False\n",
    "                except:\n",
    "                    return False\n",
    "        if len(lis) == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stk = []\n",
    "        for c in s:\n",
    "            stk.append(c)\n",
    "            if ''.join(stk[-3:]) == \"abc\":\n",
    "                stk[-3:] = []\n",
    "        return len(stk) == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        str_list = []\n",
    "        for i in s:\n",
    "            str_list.append(i)\n",
    "            if ''.join(str_list[-3:]) == 'abc':\n",
    "                str_list[-3:] = []\n",
    "        return str_list == []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if s[0] != 'a' or n // 3 * 3 != n or 'ac' in s or 'bb' in s:\n",
    "            return False\n",
    "        # 栈\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if len(stack) >= 2 and stack[-2] == 'a' and stack[-1] == 'b' and c == 'c':\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(c)\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        # n = len(s)\n",
    "        # if n // 3 * 3 != n:\n",
    "        #     return False\n",
    "\n",
    "        st = []\n",
    "        for c in map(ord, s):\n",
    "            if c > 97 and (not st or c - st.pop() != 1):\n",
    "                return False\n",
    "            if c < 99:\n",
    "                st.append(c)\n",
    "        return not st\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stack = []\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if s[i]!='c':\n",
    "                stack.append(s[i])\n",
    "                continue\n",
    "            if len(stack)<=1:\n",
    "                return False\n",
    "            if stack.pop()!='b':\n",
    "                return False\n",
    "            if stack.pop()!='a':\n",
    "                return False\n",
    "        if len(stack)==0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        s1 = \"\"\n",
    "\n",
    "        for item in s:\n",
    "            s1 += item\n",
    "            if s1.endswith(\"abc\"):\n",
    "                s1 = s1[:-3]\n",
    "\n",
    "        return s1 == ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isValid(self, s: str) -> bool:\r\n",
    "\r\n",
    "        st = []\r\n",
    "\r\n",
    "        for c in map(ord, s):\r\n",
    "            if c > ord('a') and (len(st) == 0 or c - st.pop() != 1):\r\n",
    "                return False\r\n",
    "            if c < ord('c'):\r\n",
    "                st.append(c)\r\n",
    "        \r\n",
    "        return len(st) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        temp = []\n",
    "        for i in s:\n",
    "            temp.append(i)\n",
    "           \n",
    "            if len(temp) < 3:\n",
    "                \n",
    "                continue\n",
    "            if ''.join(temp[-3:]) == 'abc':\n",
    "                temp[-3:] = []\n",
    "\n",
    "        \n",
    "        return len(temp) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        arr=''\n",
    "        for i in s:\n",
    "            if arr and arr[-3:]=='abc':\n",
    "                arr=arr[:-3]\n",
    "            arr+=i\n",
    "        return arr=='abc'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stk = []\n",
    "        for c in s:\n",
    "            stk.append(c)\n",
    "            if ''.join(stk[-3:]) == \"abc\":\n",
    "                stk[-3:] = []\n",
    "        return len(stk) == 0\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        '''\n",
    "        模式：\n",
    "        NEW = OLD_left + P + OLD_right\n",
    "        NEW = OLD + P\n",
    "        Pattern没有打撒，可以用栈\n",
    "        '''\n",
    "\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            stack.append(c)\n",
    "            if c == 'c':\n",
    "                # NOTE Pattern没有大打散，stack中元素出栈\n",
    "                if len(stack) < 3 or ''.join(stack[-3:]) != 'abc':\n",
    "                    return False\n",
    "                stack[-3:] = []\n",
    "\n",
    "        return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        # 可以使用替换的方法 -- if \"abc\" in s : s.replace(\"abc\",\"\",1)\n",
    "        \n",
    "        # while (\"abc\" in s):\n",
    "        #     s = s.replace(\"abc\",\"\",1)\n",
    "\n",
    "        # if not s: return True\n",
    "        # return False\n",
    "\n",
    "        # 使用栈的思想\n",
    "        res = []\n",
    "        for c in s:\n",
    "            res.append(c)\n",
    "            if \"\".join(res[-3:]) == \"abc\":\n",
    "                res[-3:] = []\n",
    "        return len(res)==0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stack = []\n",
    "        for c in map(ord, s):\n",
    "            if c > ord('a') and (len(stack) == 0 or c - stack.pop() != 1):\n",
    "                return False\n",
    "            if c < ord('c'):\n",
    "                stack.append(c)\n",
    "        return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        temp = ''+s\n",
    "        while len(temp)>2:\n",
    "            t_flag = False\n",
    "            for i in range(len(temp)-2):\n",
    "                if temp[i:i+3] == 'abc':\n",
    "                    temp = temp[0:i]+temp[i+3:]\n",
    "                    t_flag = True\n",
    "                    break\n",
    "            if not t_flag:\n",
    "                break    \n",
    "        return len(temp)==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        st = []\n",
    "\n",
    "        for si in s:\n",
    "            \n",
    "            if si == 'c':\n",
    "                if len(st) >= 2 and st[-1] == 'b' and st[-2] == 'a':\n",
    "                    st.pop()\n",
    "                    st.pop()\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                st.append(si)\n",
    "        if len(st) == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c=='c':\n",
    "                if ''.join(stack[-2:])+'c'=='abc':\n",
    "                    stack[-2:]=[]\n",
    "                    continue\n",
    "            stack.append(c)\n",
    "        return len(stack)==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            stack.append(c)\n",
    "            if \"\".join(stack[-3:]) == \"abc\":\n",
    "                stack[-3:] = []\n",
    "        return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isValid(self, s: str) -> bool:\r\n",
    "\r\n",
    "        st = []\r\n",
    "\r\n",
    "        for c in map(ord, s):\r\n",
    "            if c > ord('a') and (len(st) == 0 or c - st.pop() != 1):\r\n",
    "                return False\r\n",
    "            if c < ord('c'):\r\n",
    "                st.append(c)\r\n",
    "        \r\n",
    "        return len(st) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        st = []\n",
    "        for c in s:\n",
    "            if(c == 'c'):\n",
    "                if(len(st)>=2 and st[-1] == 'b' and st[-2] == 'a'):\n",
    "                    st.pop()\n",
    "                    st.pop()\n",
    "                else:\n",
    "                    st.append(c)\n",
    "            else:\n",
    "                st.append(c)\n",
    "        return st == []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stack = []\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            stack.append(s[i])\n",
    "            while stack and len(stack) >=3 and stack[-1] == \"c\" and stack[-2] == \"b\" and stack[-3] == \"a\":\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "            \n",
    "\n",
    "        if stack == []:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stack = []\n",
    "\n",
    "        for i in s:\n",
    "            if i != 'c':\n",
    "                stack.append(i)\n",
    "                \n",
    "            else:\n",
    "                if len(stack) < 2:\n",
    "                    return False\n",
    "                \n",
    "                if stack[-1] == 'b' and stack[-2] == 'a':\n",
    "                    stack.pop()\n",
    "                    stack.pop()\n",
    "\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "        return len(stack) == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stack, cur = [], ''\n",
    "        for c in s:\n",
    "            if c == 'a':\n",
    "                if cur != '':\n",
    "                    stack.append(cur)\n",
    "                cur = c\n",
    "            elif c == 'b':\n",
    "                if cur != 'a':\n",
    "                    return False\n",
    "                cur = 'ab'\n",
    "            elif c == 'c':\n",
    "                if cur != 'ab':\n",
    "                    return False\n",
    "                cur = ''\n",
    "                if len(stack) > 0:\n",
    "                    cur = stack.pop()\n",
    "        return len(stack) == 0 and cur == ''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stk = []\n",
    "        for c in s:\n",
    "            stk.append(c)\n",
    "            if \"\".join(stk[-3:]) == \"abc\":\n",
    "                stk[-3:] = []\n",
    "        return len(stk) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stack = []\n",
    "        cur = 0\n",
    "        while cur < len(s):\n",
    "            stack.append(s[cur])\n",
    "            if len(stack) >= 3 and stack[-3] == 'a' and stack[-2] == 'b' and stack[-1] == 'c':\n",
    "                for i in range(3):\n",
    "                    stack.pop()\n",
    "            cur += 1\n",
    "        if not stack: \n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stack, cur = [], ''\n",
    "        for c in s:\n",
    "            if c == 'a':\n",
    "                if cur != '':\n",
    "                    stack.append(cur)\n",
    "                cur = 'a'\n",
    "            elif c == 'b':\n",
    "                if cur != 'a':\n",
    "                    return False\n",
    "                cur = 'ab'\n",
    "            else:\n",
    "                if cur != 'ab':\n",
    "                    return False\n",
    "                cur = stack.pop() if len(stack) > 0 else ''\n",
    "        return len(stack) == 0 and cur == ''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        '''\n",
    "        栈\n",
    "        1、维护一个栈，数据依次入栈，每次入栈都检查栈顶的三个是否构成abc，构成弹出。\n",
    "        2、结束的时候如果栈中还有数据，则False，否则True\n",
    "        '''\n",
    "\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            stack.append(c)\n",
    "            if len(stack) >= 3:\n",
    "                if stack[-3:] == ['a', 'b', 'c']:\n",
    "                    stack = stack[:-3]\n",
    "\n",
    "        return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        s=list(s)\n",
    "        i = 0\n",
    "        stack = []\n",
    "        while i < n:\n",
    "            stack.append(s[i])\n",
    "            if len(stack) > 2 and stack[-1] == 'c' and stack[-2] == 'b' and stack[-3] == 'a':\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "            i += 1\n",
    "        if len(stack) == 0:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        if len(s) % 3:\n",
    "            return False\n",
    "        t = []\n",
    "        for c in s:\n",
    "            t.append(c)\n",
    "            if ''.join(t[-3:]) == 'abc':\n",
    "                t[-3:] = []\n",
    "        return not t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        a=[]\n",
    "        for i in s:\n",
    "            if len(a)<2:\n",
    "                a.append(i)\n",
    "            elif i != 'c':\n",
    "                a.append(i)\n",
    "            else:\n",
    "                if a[-1]=='b' and a[-2]=='a':\n",
    "                    a.pop()\n",
    "                    a.pop()\n",
    "                else:\n",
    "                    a.append(i)\n",
    "        return not a\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stk = []\n",
    "        for c in s:\n",
    "            stk.append(c)\n",
    "            if ''.join(stk[-3:]) == 'abc':\n",
    "                stk[-3:] = []\n",
    "        return len(stk) == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        target = ['a','b','c']\n",
    "        stack = []\n",
    "        for ch in s:\n",
    "            stack.append(ch)\n",
    "            if len(stack) >= 3:\n",
    "                if stack[-3] == 'a' and stack[-2] == 'b' and stack[-1] == 'c':\n",
    "                    for i in range(3):\n",
    "                        stack.pop()\n",
    "        return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        target = ['a','b','c']\n",
    "        stack = []\n",
    "        for ch in s:\n",
    "            stack.append(ch)\n",
    "            if len(stack) >= 3:\n",
    "                if stack[-3:] == target:\n",
    "                    for i in range(3):\n",
    "                        stack.pop()\n",
    "        return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stack = []\n",
    "        for _ in s:\n",
    "            stack.append(_)\n",
    "            if ''.join(stack[-3:]) == 'abc':\n",
    "                stack = stack[:-3]\n",
    "        return len(stack) == 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stack=[]\n",
    "        for c in s:\n",
    "            stack.append(c)\n",
    "            while len(stack)>=3 and stack[-3]=='a' and stack[-2]=='b' and stack[-1]=='c':\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "        return len(stack)==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        st = []\n",
    "        for ch in s:\n",
    "            st.append(ch)\n",
    "            if len(st) >= 3 and st[-1] == 'c' and st[-2] == 'b' and st[-3] == 'a':\n",
    "                st.pop()\n",
    "                st.pop()\n",
    "                st.pop()\n",
    "        return not st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        s_stack = list()\n",
    "        for letter in s:\n",
    "            s_stack.append(letter)\n",
    "            if len(s_stack) >= 3:\n",
    "                if s_stack[-1] == 'c' and s_stack[-2] == 'b' and s_stack[-3] == 'a':\n",
    "                    s_stack.pop()\n",
    "                    s_stack.pop()\n",
    "                    s_stack.pop()\n",
    "        if len(s_stack):\n",
    "            return False \n",
    "        else:\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stack=[]\n",
    "        for ss in s:\n",
    "            stack.append(ss)\n",
    "            if len(stack)>=3:\n",
    "                while stack[-3:]==[\"a\",\"b\",\"c\"]:\n",
    "                    stack=stack[:-3]\n",
    "        if not stack:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stack=[]\n",
    "        for i in range(len(s)):\n",
    "            stack.append(s[i])\n",
    "            while len(stack)>=3 and [stack[-3],stack[-2],stack[-1]]==['a','b','c']:\n",
    "\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "        return len(stack)==0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        indexes = []\n",
    "        s_index = -1\n",
    "        while s:\n",
    "            n = len(s)\n",
    "            while s_index < n:\n",
    "                s_index = s.find(\"abc\", s_index + 1)\n",
    "                if s_index >= 0:\n",
    "                    indexes.append(s_index)\n",
    "                else:\n",
    "                    if not indexes:\n",
    "                        return False\n",
    "                    next_s = s[:indexes[0]]\n",
    "                    for l, r in itertools.pairwise(indexes):\n",
    "                        next_s += s[l+3:r]\n",
    "                    next_s += s[indexes[-1] + 3:]\n",
    "                    indexes = []\n",
    "                    s = next_s\n",
    "                    break\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        s_list = s.split('abc')\n",
    "        while len(s_list) > 1:\n",
    "            new_s = ''.join(s_list)\n",
    "            s_list = new_s.split('abc')\n",
    "            print(s_list)\n",
    "        if  s_list != ['']:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        # 即判断s是否包含整数个可以交叉出现的abc\n",
    "        # 堆栈\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            stack.append(i)\n",
    "            if len(stack) >= 3 and ''.join(stack[-3:]) == 'abc':\n",
    "                stack = stack[:-3]\n",
    "        if len(stack) == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, s: str) -> bool:\n",
    "        stk = []\n",
    "        for c in s:\n",
    "            stk.append(c)\n",
    "            if len(stk) >= 3 and ''.join(stk[-3:]) == \"abc\":\n",
    "                stk = stk[:-3]\n",
    "        return len(stk) == 0\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
